The present invention relates generally to a data structure that may be used in network communications, and more particularly to an index for locating, or discovering, devices connected within a network.
Network discovery is a technique commonly used by gateway servers and network management servers to identify devices in a network with given characteristics, or traits, as a component of monitoring a network. Network devices generally refers to routers and switches, but may also include other networked devices, such as printers.
A Bloom filter is a memory-efficient, probabilistic data structure that supports approximate membership queries in a set. When testing whether an object is a member of a set represented by a Bloom filter, a negative response to a membership query is always true, but there is a small probability that a positive response may be false. A Bloom filter is typically implemented as a bit vector, or array, into which a set of values, representing set elements, is hashed. In general, a Bloom filter may be considered when space is at a premium and the effect of false positives can be mitigated. Due to their efficiency, compact representation, and flexibility in allowing a choice of an acceptable false positive probability at the cost of increased memory, Bloom filters are popular in representing diverse sets of data. For example, they are used in databases, distributed systems, web caching, and other network applications, where systems need to share information about what resources they have. A typical example is using a Bloom filter to reduce the incidence of disk or network lookups for non-existent objects. If the Bloom filter indicates that the object is not present, then an expensive lookup may be avoided. If the Bloom filter indicates that the object is present, a lookup may be performed, but it may fail a certain percentage of the time.
A Bloom filter index organizes a collection of Bloom filters. Searching a Bloom filter index for a target Bloom filter typically involves comparing indexed Bloom filters with the target Bloom filter to find matches. A standard, but inefficient, technique for locating a target Bloom filter in a collection of Bloom filters is to linearly search a list of all the Bloom filters in the collection for ones that match the target.